package com.xk._02算法篇._05backTracking.leetcode;

/**
 * https://leetcode.cn/problems/n-queens-ii/
 * @description: 52. N皇后 II
 * @author: xu
 * @date: 2022/10/18 15:16
 */
public class Test02 {
    public static void main(String[] args) {
        for (int i = 0; i < 12; i++) {
            System.out.println(i + " ---- " + new Test02().totalNQueens(i));
        }

    }


    private boolean[] cols;
    private boolean[] leftTop;
    private boolean[] rightTop;
    private int ways;

    public int totalNQueens(int n) {
        if (n < 1) return 0;
        cols = new boolean[n];
        leftTop = new boolean[(n << 1) - 1];
        rightTop = new boolean[leftTop.length];
        ways = 0;
        place(0);
        return ways;
    }

    /**
     * 从第 row 行开始摆放皇后
     * @param row
     */
    private void place(int row) {
        if (row == cols.length) {
            ways += 1;
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            // 剪枝处理
            if (cols[col]) continue;
            int ltIndex = row - col + cols.length - 1;
            int rtIndex = row + col;
            if (leftTop[ltIndex] || rightTop[rtIndex]) continue;

            // 在第row行，第col列摆放皇后
            cols[col] = leftTop[ltIndex] = rightTop[rtIndex] = true;
            place(row + 1);

            // 状态重置
            cols[col] = leftTop[ltIndex] = rightTop[rtIndex] = false;
        }
    }
}
